package 链表系列;

class ListNode{
    int val;            //当前节点的值
    ListNode next;  //指向下一个节点的指针/引用
    //    ListNode prev;  //指示链表中的上一个节点
    ListNode() {}

    ListNode(int val) {
        this.val = val;
        next = null;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * 单链表实现设计链表
 *     get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
 *     addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
 *     addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
 *     addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
 *     deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
 */

class MyLinkedList {

    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head;

    public MyLinkedList(){
        size = 0;
        head = new ListNode(0);
    }

    //get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
    public int get(int index) {
        if(index<0||index>=size) return -1; //若索引无效，注意索引是从0开始的，0代表第一个元素
        if(head==null)  return -1;  //防止未初始化直接调用函数,这里可以忽略因为有初始化函数
        ListNode currentNode = head;    //当前节点等于虚拟头节点
        int i = 0;
        currentNode = currentNode.next;//指向第0个元素
        while(i<index){ //i表示第i个元素
            currentNode = currentNode.next;
            i++;
        }
    	return currentNode.val;//返回第index个元素
    }

    //addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
    public void addAtHead(int val) {
        ListNode newHead = new ListNode(val);   //创建新生成的节点
        ListNode currentNode = head;            //当前节点等于虚拟头节点
        //注意！！！以下是核心语句，顺序绝对不能反
        newHead.next = currentNode.next;        //新生成的头节点的下一个元素等于当前虚拟头节点的下一个元素（这一步是使它和下一个元素串起来）
        currentNode.next = newHead;             //当前虚拟头节点的元素指向新节点（这一步是使它成为头节点）
        size++;

        /**
         * 另一种写法直接调用addAtIndex函数
         * addAtIndex(0,val);
         */
    }

    //addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
    public void addAtTail(int val) {
        int i = 0;
        ListNode currentNode = head;    //当前节点等于虚拟头节点
        while(i<size){                  //遍历链表，即使当前节点等于当前尾节点
            currentNode = currentNode.next;
            i++;
        }
        ListNode newTail = new ListNode(val);//创建新生成的节点
        newTail.next = null;//新尾节点的下一个元素等于null，这句可删
        currentNode.next = newTail; //当前尾节点的下一个元素等于新尾节点
        size++;
        /**
         * 另一种写法直接调用addAtIndex函数
         * addAtIndex(size,val);
         */
    }

    //addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
    public void addAtIndex(int index, int val) {
        if(index<0||index>size) return ;    //注意！index可以等于链表的长度！如果 index 等于链表的长度，则该节点将附加到链表的末尾。
        int j = 0;
        ListNode currentNode = head;        //当前节点等于虚拟头节点
        while(j<index){                     //遍历当前链表，找到第index-1个元素（因为是要在链表中的第 index 个节点之前添加值为 val  的节点）
            currentNode = currentNode.next;
            j++;
        }
        ListNode newTail = new ListNode(val);//创建新节点
        newTail.next = currentNode.next;    //新节点的下一个节点等于第index-1个节点的下一个节点
        currentNode.next = newTail;         //第index-1个节点的下一个节点等于新节点
        size++;
    }

    //deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
    public void deleteAtIndex(int index) {
        if(index<0||index>=size) return ;   //注意！index不可以等于链表的长度！如果 index 等于链表的长度，则越界。
        if(head==null)  return;
        int j = 0;
        ListNode currentNode = head;        //当前节点等于虚拟头节点
        while(j<index){                     //遍历当前链表，找到第index-1个元素（因为删除操作需要找到index前一个节点）
            currentNode = currentNode.next;
            j++;
        }
            currentNode.next = currentNode.next.next;   //第index-1个节点的下一个节点等于它下下一个节点（等于把第index个节点删了）
        size--;
    }

    //updateAtIndex(int index, int val)：如果索引 index 有效，则修改链表中的第 index 个节点的值等于 val 。
    public void updateAtIndex(int index, int val){
        if(index<0||index>=size) return ;    //注意！index不可以等于链表的长度！如果 index 等于链表的长度，则越界。
        int i = 0;
        ListNode currentNode = head.next;    //当前节点等于第0个节点
        while(i <index){                     //遍历当前链表，找到第index个元素（因为是要在修改第index个节点的值）
            currentNode = currentNode.next;
            i++;
        }
        currentNode.val = val;              //修改值
    }

    //updateAtVal(int oldVal, int newVal)：如果存在值为 oldVal 的节点，则修改其值等于newVal 。
    public void updateAtVal(int oldVal, int newVal){
        if(size<=0) return ;    //注意！size应大于0
        int i = 0;
        ListNode currentNode = head;        //当前节点等于虚拟头节点
        while(i < size){                     //遍历当前链表，如果存在值为 oldVal 的节点，则修改其值等于newVal 。
            currentNode = currentNode.next;
            i++;
            if(currentNode.val == oldVal){  //如果等于oldVal则修改他的值
                currentNode.val = newVal;
            }
        }
    }

    //getAtVal(index)：查找链表中第一个值为val的节点并返回它的索引值
    public int getAtVal(int val) {
        if(size <= 0)     return -1;    //注意！size应大于0
        int i = 0;
        ListNode currentNode = head;        //当前节点等于虚拟头节点
        while(i < size){                     //遍历当前链表，查找链表中第一个值为val的节点并返回它的索引值
            currentNode = currentNode.next;
            i++;
            if(currentNode.val == val){  //如果值为val的节点则返回它的索引值
                return i-1;
            }
        }
        return -1;//否则返回-1
    }

    //printAllNodeVal
    public void printAllNodeVal() {
        if(size <= 0)     return ;    //注意！size应大于0
        int i = 0;
        ListNode currentNode = head;        //当前节点等于虚拟头节点
        System.out.println("========================");
        System.out.println("链表中所有元素为：");
        while(i < size){                     //遍历当前链表，查找链表中第一个值为val的节点并返回它的索引值
            currentNode = currentNode.next;
            i++;
            System.out.println(currentNode.val);
        }
        System.out.println("========================");
    }
}
